import java.util.*;

/**
 * 128. 最长连续序列
 * https://leetcode-cn.com/problems/longest-consecutive-sequence/
 */
public class Solutions_128 {
    public static void main(String[] args) {
//        int[] nums = {100, 4, 200, 1, 3, 2};  // output: 4
//        int[] nums = {0, 3, 7, 2, 5, 8, 4, 6, 0, 1};  // output: 9
        int[] nums = {1, 2, 0, 1};  // output: 3
//        int[] nums = {2147483647, -2147483648};  // output: 1

        int result = longestConsecutive(nums);
        System.out.println(result);
    }

    /**
     * 解法三：并查集（16ms）
     */
    public static int longestConsecutive(int[] nums) {
        if (nums.length < 1) {
            return 0;
        }
        UnionFind unionFind = new UnionFind(nums);
        for (int num : nums) {
            // 合并
            // 使 num 与其默认“老大” num + 1 产生关联（若 num + 1 存在）
            // 关键：num 的最终“老大”一定是 num + 1 的最终“老大”
            unionFind.union(num, num + 1);
        }
        int res = 1;
        for (int num : nums) {
            if (num == Integer.MAX_VALUE) {
                // nums 取值只有 [Integer.MIN_VALUE, Integer.MAX_VALUE]，
                // 所以 int 最大值后面没有更大的数了
                continue;
            }
            // 查找 num 的最大“老大”
            int max = unionFind.find(num);
            // 从 num 开始的最大连续序列长度为 max - num + 1
            res = Math.max(res, max - num + 1);
        }
        return res;
    }

    /**
     * 解法二：排序（2ms）
     */
    public static int longestConsecutive3(int[] nums) {
        if (nums.length < 1) {
            return 0;
        }
        int res = 0;
        Arrays.sort(nums);
        int count = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - 1] + 1) {
                // 可以组成连续序列
                count ++;
            } else if (nums[i] == nums[i - 1]) {
                // 相同的元素，只取第一个作为连续序列中的元素，其他的相同元素则略过
                continue;
            } else {
                // 连续序列断开
                res = Math.max(res, count);
                count = 1;
            }
        }
        return Math.max(res, count);
    }

    /**
     * 解法一：Set 集合（5ms）
     */
    public static int longestConsecutive2(int[] nums) {
        Set<Integer> set = new HashSet<>();
        if (nums.length < 1) {
            return 0;
        }
        int res = 1;
        for (int num : nums) {
            // nums 中全部元素添加到 Set 中
            set.add(num);
        }
        for (int num : nums) {
            // 存在 num - 1 的元素时，需要从 num - 1 开始遍历，才能找到最长的连续序列
            if (set.contains(num - 1)) {
                continue;
            }
            int curNum = num;
            int curCount = 1;
            while (set.contains(curNum + 1)) {
                if (curNum + 1 == Integer.MIN_VALUE) {
                    // Integer.MAX_VALUE + 1 = Integer.MIN_VALUE;
                    // int 的最大值加 1 将变成 int 的最小值
                    break;
                }
                // 继续查找 curNum 后面一个数是否存在于 set 中，同时连续序列的长度加 1
                curNum ++;
                curCount ++;
            }
            // 比较得到最大长度
            res = Math.max(res, curCount);
        }
        return res;
    }
}

class UnionFind {
    // 表示从 key 开始的最长连续序列能够到达 value
    Map<Integer, Integer> parents;

    public UnionFind() {

    }
    public UnionFind(int[] nums) {
        parents = new HashMap<>();
        for (int num : nums) {
            // 初始化数组，每个元素都是各自为政，互不关联的状态
            parents.put(num, num);
        }
    }

    public Integer find(int x) {
        if (!parents.containsKey(x)) {
            return null;
        }
        // map 中查找 x 自己的“老大”是谁
        int t = parents.get(x);
        if (x != t) {
            // 如果自己不是“老大”，那么就找“老大的老大”，最终找到最大的“老大”
            parents.put(x, find(t));
        }
        // 最终返回 x 的最大“老大”
        return parents.get(x);
    }

    public boolean union(int x, int y) {
        // 找到 x 和 y 的最大“老大”
        Integer rootX = find(x), rootY = find(y);
        if (rootX == null || rootY == null) {
            return false;
        }
        if (rootX.equals(rootY)) {
            return false;
        }
        // 以上条件都满足，那么 y 的最大“老大”一定也是 x 最大“老大”的“老大”
        parents.put(rootX, rootY);
        return true;
    }
}

